import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-05-05
 * Time: 10:40
 */
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] tmp = new int [2];
        for(int i =0;i<numbers.length;++i) {
            int sum = numbers[i];
            for(int j =i+1;j<numbers.length;++j) {
                int ret = numbers[j];
                sum+=ret;
                if(sum==target){
                    tmp[0] = i+1;
                    tmp[1] = j+1;
                    Arrays.sort(tmp);
                    return tmp;
                }else {
                    sum=numbers[i];
                }
            }
        }
        return tmp;
    }
}


class Solution1 {
    public int compareVersion(String version1, String version2) {
        //思路：定义两个指针都从头开始比较
        //然后依次比较.点前面的修订号，如果指针遇到数字0，那就接着遍历到这个修订号也就是遍历到点前面的，如果没有遇到0，那就一一进行比较
        int index1 = 0 ;
        int index2 = 0 ;
        //1.1
        //1.001

        while(index1<version1.length()||index2<version2.length()) {
            if(version1.charAt(index1)=='.') {
                index1++;
            }
            if(version2.charAt(index2)=='.') {
                index2++;
            }
            while(version1.charAt(index1)==0) {
                if(version1.charAt(index1+1)=='.') {
                    break;
                }
                index1++;
            }
            //此时index1指的是要么是非0数字要么是.前面一个非0数字，要么是.前面为0
            while(version2.charAt(index2)==0) {
                if(version2.charAt(index2+1)=='.') {
                    break;
                }
                index2++;
            }
            if(version2.charAt(index2)<version1.charAt(index1)){
                return 1;
            }else if(version2.charAt(index2)>version1.charAt(index1)){
                return -1;
            }else {
                index1++;
                index2++;
            }
        }
        return 0;
    }
}

class Solution2 {
    public int compareVersion(String version1, String version2) {
        int index1 =0;
        int index2 =0;
        while(index1<version1.length()||index2<version2.length()) {
            int num1 =0;
            int num2 =0;
            while(index1<version1.length()&&version1.charAt(index1)!='.') {
                num1 = num1*10+version1.charAt(index1++)-'0';
            }
            while(index2<version2.length()&&version2.charAt(index2)!='.') {
                num2 = num2*10+version2.charAt(index2++)-'0';
            }
            //此时比较.号前面的修订号大小
            if(num1>num2){
                return 1;
            }else if(num1<num2){
                return -1;
            }else {
                index1++;
                index2++;
            }
        }
        return 0;
    }
}


class Solution3 {
    public int compareVersion(String version1, String version2) {
        int index1 =0;
        int index2 =0;
        while(index1<version1.length()||index2<version2.length()) {
            int num1 =0;
            int num2 =0;
            while(index1<version1.length()&&version1.charAt(index1)!='.') {
                num1 = version1.charAt(index1++)-'0';
            }
            while(index2<version2.length()&&version2.charAt(index2)!='.') {
                num2 = version2.charAt(index2++)-'0';
            }
            //此时比较.号前面的修订号大小
            if(num1>num2){
                return 1;
            }else if(num1<num2){
                return -1;
            }else {
                index1++;
                index2++;
            }
        }
        return 0;
    }
}
class Solution4 {
    public int compareVersion(String version1, String version2) {
        String[] s1 = version1.split("\\.");
        String[] s2 = version2.split("\\.");
        int index1 = 0;
        int index2 =0;
        int m =s1.length;
        int n =s2.length;
        while(index1<m||index2<n) {
            int a=0;
            int b =0;
            //将index1转化为整数
            if(index1<m)
                a = Integer.parseInt(s1[index1++]);
            if(index2<n)
                b = Integer.parseInt(s2[index2++]);
            if(a!=b){
                return a>b?1:-1;
            }
        }
        return 0;
    }
}

class Solution6 {
    public int compress(char[] chars) {
        int left =0;
        int right =0;
        int len = chars.length;
        while(right<len) {
            int index =right;
            while(right<len&&chars[index]==chars[right]) {
                right++;
            }
            int repeats = right-index;
            chars[left]=chars[right-1];
            if(repeats==1){
                left++;
            }else if(repeats<=9){
                //将repeats数字转化成字符放到chars[left]位置上去
                char ch = (char)(repeats+'0');
                chars[left+1] = ch;
                left+=2;
            }else {
                //>9 10  11  1000
                String s = repeats+"";
                for(int i =0;i<s.length();++i){
                    chars[left+1+i] = s.charAt(i);
                }
                left+=s.length()+1;
            }
        }
        return left;
    }
}

class Solution7 {
    public int compress(char[] cs) {
        int n = cs.length;
        int i = 0, j = 0;
        while (i < n) {
            int idx = i;
            while (idx < n && cs[idx] == cs[i]) idx++;
            int cnt = idx - i;
            cs[j++] = cs[i];
            if (cnt > 1) {
                int start = j, end = start;
                while (cnt != 0) {
                    cs[end++] = (char)((cnt % 10) + '0');
                    cnt /= 10;
                }
                reverse(cs, start, end - 1);
                j = end;
            }
            i = idx;
        }
        return j;
    }
    void reverse(char[] cs, int start, int end) {
        while (start < end) {
            char t = cs[start];
            cs[start] = cs[end];
            cs[end] = t;
            start++; end--;
        }
    }
}


class Solution8 {
    public int characterReplacement(String s, int k) {
        int left = 0;//滑动窗的左窗口
        int right = 0;//滑动窗的右窗口
        int len = s.length();
        int cnt =0;
        int differNum =0;
        while(right<len) {
            char cL = s.charAt(left);
            char cR = s.charAt(right);
            if(cL==cR){//相同
                right++;
            }else {//不相同
                ++differNum;
                if(differNum<k){
                    right++;
                    cnt = Math.max(cnt,right - left);
                }else {
                    cnt = Math.max(cnt,right - left);
                    left++;
                    right++;
                    differNum=0;
                }
            }
        }
        return cnt;
    }
}
public class TestLeetCode {

    public static void main(String[] args) {
        Solution8 solution8 = new Solution8();
        solution8.characterReplacement("AABABBA",1);
    }


    public static void main7(String[] args) {
        Solution7 solution7 = new Solution7();
        char[] chars = {'a','a','a','b','b','a','a'};
        solution7.compress(chars);

//        Solution6 solution6 = new Solution6();
//        char[] chars = {'a','a','a','b','b','a','a'};
//        solution6.compress(chars);
    }
    public static void main6(String[] args) {
        String s1 = "741852963";
        System.out.println(s1.substring(0, 1));
    }

    public static void main5(String[] args) {
        Solution4 solution4 = new Solution4();
        solution4.compareVersion("1.01","1.001");
    }

    public static void main4(String[] args) {
        String s = "0000123";

        int a = Integer.parseInt(s);
        System.out.println(a);
    }

    public static void main2(String[] args) {
        Solution3 solution = new Solution3();
        solution.compareVersion("1.1","1.10");
    }

//    public static void main(String[] args) {
//        Solution solution = new Solution();
//        int[] array = {2,3,4,5,6,7,8,9,41,56,78,89};
//        System.out.println(Arrays.toString(solution.twoSum(array, 91)));
//    }

    public static void main1(String[] args) {

    }

}
